【2018 国庆雅礼 NOIP 培训】D1T3 画作（paint）

发表于

题面在这里

不难 证明 猜到一个这样的结论:

存在一种最优方案使得每次操作的区域是上一次的子集且颜色与上一次相反。

考虑归纳证明, 记 S 为当前所有操作区域的并, T 为接下来一步的操作 区域,

我们有:

1. T 与 S 有交的情况一定可以转化成 T 被 S 包含的情况。

2. T 与 S 交集为空时, 可以找一个连接 S 和 T 的集合 M 并操作 S ∪ T ∪M, 并将之前的所有操作连接到更外的层以及外层的连接部分同时 操作, 特殊处理最外层和第二层的情况。

3. T 被 S 包含时, T 落在某个完整区域内时等价于情况二, 否则一定连 接若干个同色块, 这些块可以同时处理, 步数一定不会更劣。

知道这个结论就比较好做了虽然我不知道, 我们可以枚举最后被修改的区域, 这时答 案就是将同色边边权当作 0, 异色边边权当作 1 后距离这个点最远的黑色点 的距离, 对所有点取最小值就可以了。（然而我并没有A了这道题qwq）

以下代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>

using std::pair;
using std::vector;
using std::string;

typedef long long ll;
typedef pair<int, int> pii;

#define fst first
#define snd second
#define pb(a) push_back(a)
#define mp(a, b) std::make_pair(a, b)

template <typename T> bool chkmax(T& a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> bool chkmin(T& a, T b) { return a > b ? a = b, 1 : 0; }

const int oo = 0x3f3f3f3f;

template <typename T> T read(T& x) {
    int f = 1; x = 0;
    char ch = getchar();
    for(;!isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
    for(; isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
    return x *= f;
}

const int N = 50;

int n, m;
char g[N + 5][N + 5];
int dis[N + 5][N + 5];

const int dx[] = { 1, 0, -1, 0 };
const int dy[] = { 0, 1, 0, -1 };

int bfs(int x, int y) {
    std::deque<pii> q;
    memset(dis, -1, sizeof dis);

    dis[x][y] = 0;
    q.push_back(mp(x, y));

    int res = 0;
    while(!q.empty()) {
        int cx = q.front().fst, cy = q.front().snd;

        if(g[cx][cy] == '1')
            chkmax(res, dis[cx][cy]);

        q.pop_front();
        for(int i = 0; i < 4; ++i) {
            int nx = cx + dx[i], ny = cy + dy[i];

            if(nx >= 0 && nx < n && ny >= 0 && ny < m && dis[nx][ny] == -1) {

                if(g[nx][ny] == g[cx][cy]) {
                    dis[nx][ny] = dis[cx][cy];
                    q.push_front(mp(nx, ny));
                } else {
                    dis[nx][ny] = dis[cx][cy] + 1;
                    q.push_back(mp(nx, ny));
                }
            }
        }
    }
    return res;
}

int main(){
    read(n), read(m);
    for(int i = 0; i < n; ++i) {
        scanf("%s", g[i]);
    }

    int ans = oo;
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            chkmin(ans, bfs(i, j));
        }
    }
    printf("%d\n", ans + 1);

    return 0;
}